题解 51nod有限背包计数问题

发表于 | 更新于

题目链接

很考验对背包的理解

对于$1$~$sqrt(n)$与$(sqrt(n)+$$1)$~$n,$我们可以用NOIP2001数的划分的类似做法，分别处理，显然$1$~$sqrt(n)$是个多重背包问题，$(sqrt(n)+$$1)$~$n$是个完全背包问题

对于$1$~$sqrt(n)$，我们可以用总方案数减去不合法的方案数(具体见代码注释)，并利用滚存优化空间

对于$(sqrt(n)+$$1)$~$n,$我们可以用NOIP2001数的划分的类似做法，将划分分成两种类型，进行$dp$转移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
#define ll long long
#define re register
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
   int x=0,w=0;char ch=getchar();
   while (!isdigit(ch))w|=ch=='-',ch=getchar();
   while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
   return w?-x:x;
}
int f[2][393939],g[319][100007],ans;
signed main(){
//    freopen("game.in", "r", stdin); freopen("game.out", "w", stdout); 
    int n=read(),mod=read();
    f[0][0]=1;//选0个的方案数为1 
    int sq=sqrt(n),now=0;
    for (int i=1;i<=sq;++i){
        now^=1;//滚存 
        for (int j=0;j<=n;++j){
            f[now][j]=f[now^1][j];//加上i-1的方案种数 
            if (j>=i)f[now][j]+=f[now][j-i];//完全背包方案数的递推式 
            if (f[now][j]>=mod)f[now][j]-=mod;
            if (j>=i*(i+1))f[now][j]=f[now][j]-f[now^1][j-i*(i+1)]+mod;//减去不符合的方案数，即不在j-i*i到j范围内的方案数 
            if (f[now][j]>=mod)f[now][j]-=mod;
        }
    }//前sqrt(n)个数进行多重背包计算方案 
//g[i][j]表示选了i个,而不是选到第i种，和为j的方案数，注意i的含义与f[i][j]中的i的含义不一样 
//类似NOIP2001数的划分的做法,所有划分成两种：
//1.包含sqrt(n)+1(即最小的数)
//2.不包含sqrt(n)+1的
//一个dp状态的方案数就是由这两种划分构成的
//对于第一种划分，只需要单独加上一份sqrt(n)+1即可，所以划分数等于f[i-1][j-(sqrt(n)+1)];
//对于第二种划分，只需要给当前每份都加上1，每份就不可能等于sqrt(n)+1了，因为最小就是sqrt(n)+1,所以划分数就等于f[i][j+i];
    g[0][0]=1;//选0个，和为0的方案数为1 
    if (sq+1<=n)g[1][sq+1]=1;//选1个sqrt(n)+1(最小值) 
    for (int i=1;i<=sq;++i){
        for (int j=0;j<=n;++j){
            if (j+sq+1<=n)g[i+1][j+sq+1]+=g[i][j];//第一种划分 
            if (g[i+1][j+sq+1]>=mod)g[i+1][j+sq+1]-=mod; 
            if (j+i<=n)g[i][j+i]+=g[i][j];//第二种划分 
            if (g[i][j+i]>=mod)g[i][j+i]-=mod;
        }
    }
    for (int i=0;i<=n;++i)
        for (int j=0;j<=sq;++j){
            ans+=1ll*f[now][i]*g[j][n-i]%mod;// 最后枚举多少空间给前sqrt(n)个物品(剩下空间给其它物品)
            if (ans>=mod)ans-=mod;
        }
    printf("%d",ans);
    return 0;
}